/* 

  二叉搜索树(BST),又称二叉排序树或二叉查找树
*/

//封装:

function BinarySearchTree() {
  function Node(key) {
    this.key = key
    this.left = null
    this.right = null
  }

  this.root = null

  // 提供给外部使用的插入方法
  BinarySearchTree.prototype.insert = function (key) {
    // 1. 创建新结点
    let newNode = new Node(key)

    // 2.判断有没有根节点
    if (this.root) {
      this.insertNode(this.root, newNode)
    } else {
      this.root = newNode
    }
  }
  // 内部递归调用插入
  BinarySearchTree.prototype.insertNode = function (node, newNode) {
    // 1. 比较大小
    if (node.key > newNode.key) {
      // 判断左子结点是否存在
      if (node.left) {
        this.insertNode(node.left, newNode)
      } else {
        node.left = newNode
      }
    } else {
      // 判断右子节点是否存在
      if (node.right) {
        this.insertNode(node.right, newNode)
      } else {
        node.right = newNode
      }
    }
  }

  /* 
    二叉搜索树的遍历(针对树的遍历,都可以)
    1. 前序遍历 preOrderTraversal
    2. 中序遍历 inOrderTraversal
    3. 后序遍历 postOrderTraversal
    4. 层序遍历(队列实现)

  */

  // 前序遍历
  BinarySearchTree.prototype.preOrderTraversal = function (handler) {
    this.preOrderTraversalNode(this.root, handler)
  }
  BinarySearchTree.prototype.preOrderTraversalNode = function (node, handler) {
    if (!node) return false
    handler(node)
    // 遍历左子节点
    this.preOrderTraversalNode(node.left, handler)
    // 遍历右子节点
    this.preOrderTraversalNode(node.right, handler)
  }

  // 中序遍历
  BinarySearchTree.prototype.inOrderTraversal = function (handler) {
    this.inOrderTraversalNode(this.root, handler)
  }
  BinarySearchTree.prototype.inOrderTraversalNode = function (node, handler) {
    if (!node) return false
    // 遍历左子节点
    this.inOrderTraversalNode(node.left, handler)
    // 访问结点操作
    handler(node)
    // 遍历右子节点
    this.inOrderTraversalNode(node.right, handler)
  }

  // 后序遍历
  BinarySearchTree.prototype.postOrderTraversal = function (handler) {
    this.postOrderTraversalNode(this.root, handler)
  }
  BinarySearchTree.prototype.postOrderTraversalNode = function (node, handler) {
    if (!node) return false
    // 遍历左子节点
    this.postOrderTraversalNode(node.left, handler)

    // 遍历右子节点
    this.postOrderTraversalNode(node.right, handler)

    // 访问结点操作
    handler(node)
  }

  //获取最大值

  BinarySearchTree.prototype.max = function () {
    if (!this.root) {
      return null
    }
    let rightNode = this.root.right
    let retNode = this.root
    while (rightNode) {
      retNode = rightNode
      rightNode = rightNode.right
    }
    return retNode
  }

  // 最小值
  BinarySearchTree.prototype.min = function () {
    if (!this.root) {
      return null
    }
    let leftNode = this.root.left
    let retNode = this.root
    while (leftNode) {
      retNode = leftNode
      leftNode = leftNode.left
    }
    return retNode
  }
  // 搜索
  BinarySearchTree.prototype.search = function (key) {
    let node = this.root
    while (node) {
      if (node.key == key) {
        return node
      }
      // 向左遍历
      if (node.key > key) {
        node = node.left
      } else {
        node = node.right
      }
    }
  }
  // 删除
  BinarySearchTree.prototype.remove = function (key) {}
}

const bTree = new BinarySearchTree()
bTree.insert(11)
bTree.insert(7)
bTree.insert(15)
bTree.insert(5)
bTree.insert(3)
bTree.insert(9)
bTree.insert(8)
bTree.insert(10)
bTree.insert(13)
bTree.insert(12)
bTree.insert(14)
bTree.insert(20)
bTree.insert(18)
bTree.insert(25)
bTree.insert(6)

// bTree.postOrderTraversal(({ key }) => {
//   console.log(key)
// })

console.log(bTree.max())
console.log(bTree.min())
console.log(bTree.search(10))
